import random
import math


def assign_cluster(x, c):
    """
    将数据点x分配到最近的聚类中心
    
    参数:
        x: 数据点（列表或元组）
        c: 聚类中心列表
    
    返回:
        最近的聚类中心的索引
    """
    min_dist = float('inf')
    cluster_idx = 0
    
    for i, center in enumerate(c):
        # 计算欧氏距离
        dist = math.sqrt(sum((x[j] - center[j]) ** 2 for j in range(len(x))))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    
    return cluster_idx


def Kmeans(data, k, epsilon, iteration):
    """
    K均值聚类算法
    
    参数:
        data: 数据点列表，每个数据点是一个列表或元组
        k: 聚类数量
        epsilon: 收敛阈值
        iteration: 最大迭代次数
    
    返回:
        clusters: 每个数据点所属的聚类索引列表
        centers: 最终的聚类中心列表
    """
    if len(data) == 0 or k <= 0:
        return [], []
    
    # 初始化聚类中心（随机选择k个数据点）
    centers = [list(data[i]) for i in random.sample(range(len(data)), min(k, len(data)))]
    
    for _ in range(iteration):
        # 分配每个数据点到最近的聚类中心
        clusters = [assign_cluster(x, centers) for x in data]
        
        # 计算新的聚类中心
        new_centers = []
        for i in range(k):
            # 找到属于第i个聚类的所有点
            cluster_points = [data[j] for j in range(len(data)) if clusters[j] == i]
            
            if len(cluster_points) > 0:
                # 计算均值作为新中心
                new_center = [sum(point[d] for point in cluster_points) / len(cluster_points) 
                             for d in range(len(data[0]))]
                new_centers.append(new_center)
            else:
                # 如果某个聚类没有点，保持原中心
                new_centers.append(centers[i])
        
        # 检查是否收敛
        max_change = max(math.sqrt(sum((centers[i][d] - new_centers[i][d]) ** 2 
                                      for d in range(len(centers[i]))))
                        for i in range(k))
        
        if max_change < epsilon:
            break
        
        centers = new_centers
    
    return clusters, centers


# 测试示例
if __name__ == "__main__":
    # 示例数据
    data = [
        [1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11],
        [8, 2], [10, 2], [9, 3], [2, 1], [5, 5], [6, 6]
    ]
    
    k = 3
    epsilon = 0.01
    max_iter = 100
    
    clusters, centers = Kmeans(data, k, epsilon, max_iter)
    
    print("聚类结果:")
    for i, cluster_id in enumerate(clusters):
        print(f"数据点 {data[i]} -> 聚类 {cluster_id}")
    
    print("\n聚类中心:")
    for i, center in enumerate(centers):
        print(f"聚类 {i}: {center}")
